#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <utility>
#ifdef _WIN32
#include <windows.h>
#endif
using namespace std;

struct Edge { int u, v; int w; };

struct DSU {
    vector<int> p, r;
    DSU(int n=0){init(n);} 
    void init(int n){ p.resize(n); r.assign(n,0); iota(p.begin(), p.end(), 0);} 
    int find(int x){ return p[x]==x? x : p[x]=find(p[x]); }
    bool unite(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(r[a]<r[b]) swap(a,b); p[b]=a; if(r[a]==r[b]) r[a]++; return true; }
};

pair<int, vector<Edge>> kruskal(int n, vector<Edge> edges) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){return a.w < b.w;});
    DSU dsu(n);
    int total = 0; vector<Edge> used;
    for (auto &e : edges) {
        if (dsu.unite(e.u, e.v)) { total += e.w; used.push_back(e); }
    }
    return {total, used};
}

pair<int, vector<Edge>> prim(int n, const vector<vector<pair<int,int>>>& g, int start=0) {
    vector<int> vis(n,0);
    using T = tuple<int,int,int>; // w,u,v
    priority_queue<T, vector<T>, greater<T>> pq;
    vis[start]=1;
    for (auto [v,w] : g[start]) pq.emplace(w, start, v);
    int total=0; vector<Edge> used;
    while(!pq.empty() && (int)used.size()<n-1){
        auto [w,u,v]=pq.top(); pq.pop();
        if(vis[v]) continue;
        vis[v]=1; total+=w; used.push_back({u,v,w});
        for(auto [to,ww]: g[v]) if(!vis[to]) pq.emplace(ww, v, to);
    }
    return {total, used};
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
#ifdef _WIN32
    // Ensure UTF-8 output/input in Windows console
    SetConsoleOutputCP(CP_UTF8);
    SetConsoleCP(CP_UTF8);
#endif
    // 示例无向图(0..5)
    int n = 6;
    vector<Edge> edges = {
        {0,1,4},{0,2,3},{1,2,1},{1,3,2},{2,3,4},{3,4,2},{4,5,6}
    };
    // 邻接表（无向图）
    vector<vector<pair<int,int>>> g(n);
    for (auto &e: edges){ g[e.u].push_back({e.v,e.w}); g[e.v].push_back({e.u,e.w}); }

    auto [k_total, k_edges] = kruskal(n, edges);
    cout << "Kruskal MST 总权值 " << k_total << "\n边集：" << '\n';
    for (auto &e: k_edges) cout << e.u << "-" << e.v << " (" << e.w << ")\n";

    auto [p_total, p_edges] = prim(n, g, 0);
    cout << "\nPrim MST 总权值 " << p_total << "\n边集：" << '\n';
    for (auto &e: p_edges) cout << e.u << "-" << e.v << " (" << e.w << ")\n";

    return 0;
}

